package Server.map;


import java.util.Hashtable;
import java.util.Random;
import java.util.Vector;

import Server.players.Carnivorous;
import Server.players.Dino;
import Server.players.Herbivorous;
import Server.players.Player;

import common.UserMap;
import common.UserMap.BoxType;

/**
 * La Mappa contiene la lista di TUTTE le caselle e tiene traccia del posizionamento di TUTTI i dinosauri
 * @author Flavio Ferrara & Alessandro Frigerio (per l'algoritmo di creazione casuale della mappa)
 *
 */


public class Map {

	public static final int SIZE = 40;
	private BoxField boxes;
	/**
	 * foodBoxes SUBSET of boxes
	 */
	private Vector<Box> foodBoxes; 

	private Hashtable<Box, Dino> dinos;
	private Random intGenerator;

	private Hashtable<Player, UserMap> userMaps;

	public Map(char[][] data){
		this.boxes = new BoxField(SIZE, 0, SIZE - 1);
		this.foodBoxes = new Vector<Box>();
		this.dinos = new Hashtable<Box, Dino>();		
		this.userMaps = new Hashtable<Player, UserMap>();

		if (data == null){
			data = this.generateMap();
		}
		for (int i = 0;i < SIZE;i++){
			for (int j = 0;j < SIZE;j++){

				switch (data[i][j]){
				case 'a':
					this.boxes.setBox(new Box(i, j, true));
					break;
				case 't':
					// TERRA
					this.boxes.setBox(new Box(i, j, false));
					break;
				case 'v':
					// VEGETAZIONE
					Box b = new Box(i, j, false);
					b.putVegetable();
					this.boxes.setBox(b);
					this.foodBoxes.add(b);
					break;
				case 'c':
					// CAROGNA
					b = new Box(i, j, false);
					b.putMeat();
					this.boxes.setBox(b);
					this.foodBoxes.add(b);
					break;
				default:
					throw new IllegalArgumentException();
				}
			}
		}
	}


	/*
	 * helper
	 */


	public char[][] generateMap(){

		char[][] data = new char[SIZE][SIZE];	
		this.intGenerator = new Random();

		createBoard(data);
		createLand(data);
		createWater(data);
		createVegetable(data);
		createMeat(data);

		return data;
	}

	//CREAZIONE ACQUA ESTERNA
	private void createBoard(char[][] data){

		int x, y;
		for (x = 0; x < SIZE;x++){
			data[x][0] = 'a';
			data[x][SIZE-1] = 'a';
		}
		for (y = 0; y < SIZE;y++){
			data[0][y] = 'a';
			data[SIZE-1][y] = 'a';
		}
	}

	//CREAZIONE TERRA
	private void createLand(char[][] data){

		int x, y;
		for (x = 1 ; x < SIZE-1 ; x++){
			for (y = 1 ; y < SIZE-1; y++){	
				data[x][y] = 't';
			}
		}


	}

	private void createWater(char[][] data){
		int waterCount = (int) ((SIZE * SIZE * 0.2) - ((int)Math.pow(SIZE, 2) - (int)Math.pow(SIZE - 1, 2)));
		int count = 0;
		while (count < waterCount){
			int x = this.intGenerator.nextInt(SIZE);
			int y = this.intGenerator.nextInt(SIZE);

			/* si comincia */
			try{ // se sono sul bordo scatterà una IndexOutOfBounds
				// se non c'è acqua dentro o vicino
				if (data[x][y] == 'a' || 
						data[x-1][y] == 'a' || 
						data[x][y-1] == 'a' || 
						data[x+1][y] == 'a' || 
						data[x][y+1] == 'a'){ 
					continue;
				}

				data[x][y] = 'a'; // comincio la mia pozza di 5 cosi
				int innerCount = 1, tentativi = 0;
				while (innerCount < 5 && tentativi < 5000){
					tentativi++;

					int direction = this.intGenerator.nextInt(4);
					int nextX = x, nextY = y;

					// per ogni direzione devo controllare tralasciando il mio precedente
					switch (direction){ // vediamo dove vado
					case 0:
						nextX++;
						// se non c'è acqua vicino o dentro(se è tornato indietro)
						if (data[nextX][nextY] == 'a' || 
								data[nextX][nextY-1] == 'a' || 
								data[nextX+1][nextY] == 'a' || 
								data[nextX][nextY+1] == 'a'){ 
							continue;
						}
						break;
					case 1:
						nextX--;
						// se non c'è acqua vicino o dentro(se è tornato indietro)
						if (data[nextX][nextY] == 'a' ||
								data[nextX-1][nextY] == 'a' || 
								data[nextX][nextY-1] == 'a' || 
								data[nextX][nextY+1] == 'a'){ 
							continue;
						}
						break;
					case 2:
						nextY++;
						// se non c'è acqua vicino o dentro(se è tornato indietro)
						if (data[nextX][nextY] == 'a' ||
								data[nextX-1][nextY] == 'a' || 
								data[nextX+1][nextY] == 'a' || 
								data[nextX][nextY+1] == 'a'){ 
							continue;
						}
						break;
					case 3:
						nextY--;
						// se non c'è acqua vicino o dentro(se è tornato indietro)
						if (data[nextX][nextY] == 'a' ||
								data[nextX-1][nextY] == 'a' || 
								data[nextX][nextY-1] == 'a' || 
								data[nextX+1][nextY] == 'a'){ 
							continue;
						}
						break;
					}


					// allora si
					x = nextX;
					y = nextY;
					data[x][y] = 'a';
					innerCount++;
				}

				// bella per la pozza
				count += innerCount;
			} catch (IndexOutOfBoundsException e){
				continue;
			}
		}
	}


	/** CONGELATA	
	//CREAZIONE ACQUA TOTALE
	private void createWater(char[][] data){



		Integer water = 0;
		Vector <int[]> firstHistory = new Vector<int[]>(0 , 1);
		Vector <int[]> secondHistory = new Vector<int[]>(0 , 1);

		//FINCHE' NON HO AGGIUNTO TUTTA L'ACQUA
		while (water < ((20*(SIZE*SIZE)/100) - ((SIZE-1)*4))){  

		 Boolean started = false;
		 Boolean finished = false;
		 firstHistory.removeAllElements();				
		 secondHistory.removeAllElements();


			//SE MANCANO AL PIU' 15 CASELLE D'ACQUA
			if ((((20*(SIZE*SIZE)/100) - ((SIZE-1)*4)) - water) < 16){


				while (!started){
					started = createFirstWater(data , firstHistory ,  20*(SIZE*SIZE)/100 - ((SIZE-1)*4) - water , finished , water);
					while (!finished){
						finished = checkPuddles(data , firstHistory ,  water);							
					}
				}
			}

			//SE MANCANO MENO DI 20 MA PIU' DI 15 CASELLE
			if (20 > (((20*(SIZE*SIZE)/100) - ((SIZE-1)*4)) - water) &&
					((((20*(SIZE*SIZE)/100) - ((SIZE-1)*4)) - water)) > 15){



				while(!started){
					started = createFirstWater(data , firstHistory , 5 , finished , water);
					while (!finished){
						finished = checkPuddles(data , firstHistory , water);	
					}	
				}	



				while(!started){
					started = createFirstWater(data , firstHistory , 5 , finished , water);
					while(!finished){
						createRandomWater(data , secondHistory , 20*(SIZE*SIZE)/100 - ((SIZE-1)*4) - water , water);
						firstHistory.addAll(secondHistory);
						finished = checkPuddles(data , firstHistory , water);
						}
					}
				}


			//QUANDO MANCANO ANCORA MOLTE CASELLE D'ACQUA..
			while(!started){
				started = createFirstWater(data , firstHistory , 5 , finished , water);
				while(!finished){
					createRandomWater(data, secondHistory , this.intGenerator.nextInt(15) , water);
					for(int[] toAdd : secondHistory) firstHistory.add(toAdd);
					finished = checkPuddles(data , firstHistory , water);
				}


			}
		}

	}


	 * 
@param finished

//PRIMA PARTE DELLA CREAZIONE DI UNA POZZA		
private boolean createFirstWater(char[][] data , Vector<int[]> firstHistory , int minimumSize , boolean finished , Integer water){
		int i , nextDirection;
		int x , y;
		boolean deletable = false;

		x = this.intGenerator.nextInt((SIZE-1));
		y = this.intGenerator.nextInt((SIZE-1));

		//SE  E' CAPITATA UNA CASELLA CON ACQUA RICOMINCIA	
		if (data[x][y] == 'a'){
			finished = true;	//RICOMINCIA A CREARE
			return false;
		}				

		// SE E' CAPITATA UNA CASELLA VICINA AD UNA A PRECEDENTEMENTE CREATA
		if (data[x][y+1] == 'a' || data[x+1][y] == 'a'  || data[x][y-1] == 'a'  || data[x-1][y] == 'a' ){
			finished = true; 	//RICOMINCIA A CREARE
			return false;
		}



		data[x][y] = 'a';	// INSERISCI LA PRIMA DI ALMENO ALTRE 5 A
		int[] box = new int[2];
		box[0] = x;
		box[1] = y;
		firstHistory.add(box);	//AGGIUNGI ALLO STORICO DELLA POZZA
		water++;

		//CREAZIONE DELLE SUCCESSIVE 4 A 
		for (i = 1; i < minimumSize ; i++){	
			nextDirection = this.intGenerator.nextInt(3);	//SCELTA DELLA DIREZIONE PER LA PROSSIMA A
			switch (nextDirection){  
				case 0: {				//UP
					y++;
					break;
				}
				case 1:{				//RIGHT
					x++;
					break;
				}
				case 2:{				//DOWN
					y--;
					break;
				}
				case 3:{				//LEFT
					x--;
					break;
				}
			}

			// SE E' CAPITATA UNA CASELLA VICINA AD UNA A PRECEDENTEMENTE CREATA	

			if ((data[x][y+1] == 'a' && nextDirection != 2 ) ||
					(data[x+1][y] == 'a'  && nextDirection != 3) ||
						(data[x][y-1] == 'a' && nextDirection != 0) ||
							(data[x-1][y] == 'a' && nextDirection != 1)){


				//MA NON DELLA POZZA IN COSTRUZIONE
				ListIterator<int[]> controlIterator = firstHistory.listIterator();
				int[] toControl = {0 , 0};
				while(controlIterator.hasNext()){
					toControl= controlIterator.next();
					if (toControl[0] == x && toControl[1] == y+1){deletable = false;}
					else if (toControl[0] == x+1 && toControl[1] == y){deletable = false;}
					else if (toControl[0] == x && toControl[1] == y-1){deletable = false;}
					else if (toControl[0] == x-1 && toControl[1] == y){deletable = false;}
					else deletable = true;
				}
			}

				//ELIMINAZIONE POZZA IN CORSO DI COSTRUZIONE	
			if (deletable){

			ListIterator<int[]> iterator = firstHistory.listIterator();
			int[] toDelete;
			water = water - firstHistory.size();
				while(iterator.hasNext()){					
					toDelete = iterator.next();
					iterator.remove();
					data[toDelete[0]][toDelete[1]] = 't';
				}
				finished = true;	//RICOMINCIA A CREARE
				return false;
			}

			data[x][y] = 'a';
			box = new int[2];
			box[0] = x;
			box[1] = y;
			firstHistory.add(box);
			water++;
		}
		finished = false;	//PASSA ALLA SECONDA PARTE
		this.endOfFirstWater = box;
		return true;


	}

	//EVENTUALE SECONDA PARTE	
	private void createRandomWater(char [][] data , Vector<int[]> secondHistory, int randomGeneratedNumber , Integer water){

		int x = this.endOfFirstWater[0];
		int y = this.endOfFirstWater[1];
		boolean deletable = false;

		if (randomGeneratedNumber  < 1) { return; }

		int i , nextDirection;
			for (i = 0; i < randomGeneratedNumber ; i++){
				nextDirection = this.intGenerator.nextInt(3);
				switch (nextDirection){  
					case 0: {				//UP
						y++;
						break;
					}
					case 1:{				//RIGHT
						x++;
						break;
					}
					case 2:{				//DOWN
						y--;
						break;
					}
					case 3:{				//LEFT
						x--;
						break;
					}
				}

				//SE E' CAPITATA UNA CASELLA VICINA AD UNA A PRECEDENTEMENTE CREATA , MA NON A QUELLA APPENA CREATA


				if ((data[x][y+1] == 'a' && nextDirection != 2 ) ||
						(data[x+1][y] == 'a'  && nextDirection != 3) ||
							(data[x][y-1] == 'a' && nextDirection != 0) ||
								(data[x-1][y] == 'a' && nextDirection != 1)){


					//O AD UNA DELLA POZZA IN COSTRUZIONE
					ListIterator<int[]> controlIterator = secondHistory.listIterator();
					int[] toControl = {0 , 0};
					while(controlIterator.hasNext()){
						toControl= controlIterator.next();
						if (toControl[0] == x && toControl[1] == y+1){deletable = false;}
						else if (toControl[0] == x+1 && toControl[1] == y){deletable = false;}
						else if (toControl[0] == x && toControl[1] == y-1){deletable = false;}
						else if (toControl[0] == x-1 && toControl[1] == y){deletable = false;}
						else deletable = true;
					}
				}

				//ELIMINAZIONE POZZA IN CORSO DI COSTRUZIONE	

				if (deletable == true){
					ListIterator<int[]> eraseIterator = secondHistory.listIterator();
					int[] toDelete;
					water = water - secondHistory.size();
					while(eraseIterator.hasNext()){					
						toDelete = eraseIterator.next();
						data[toDelete[0]][toDelete[1]] = 't';
						eraseIterator.remove();
					}
					return;
				}


			data[x][y] = 'a';
			int[] box = new int[2];
			box[0] = x;
			box[1] = y;
			secondHistory.add(box);
			water++;

		}
	}

	//CONTROLLO POZZA APPENA CREATA	
	private boolean checkPuddles(char[][] data , Vector<int[]> toCheckHistory , Integer water){
	int x , y;
		int[] min = {SIZE , SIZE};
		int[] max = {0 , 0};

		//DEFINIZIONE DELL' AREA DA CONTROLLARE
		ListIterator<int[]> iterator = toCheckHistory.listIterator();
		int[]toCompare = {0 , 0};
		while(iterator.hasNext()){ 					
			toCompare = iterator.next();
			if (toCompare[0] < min[0] && toCompare[1] < min[1]) min = toCompare;
			if (toCompare[0] > max[0] && toCompare[1] > max[1]) max = toCompare;
		}

		int[] alreadyControlled = {0 , 0};
		boolean stopControl = false;
		int nextLandCount = 0;
		int nextWaterCount = 0;
		for(x = min[0] ; x <= max[0] ; x++){
			for(y = min[1] ; y <= max[1] ; y++){
				if (data[x][y] == 't'){
					while (!stopControl){
						for (nextLandCount = 0 ; nextLandCount == 3 ; nextLandCount++){
							if (data[x][y+1] == 't' && !(x == alreadyControlled[0] && y+1 == alreadyControlled[1])){
								alreadyControlled[0] = x;
								alreadyControlled[1] = y;
								y++;
								continue;
							}
							if (data[x][y+1] == 'a')nextWaterCount++;

							if (data[x+1][y] == 't' && !(x+1 == alreadyControlled[0] && y == alreadyControlled[1])){
								alreadyControlled[0] = x;
								alreadyControlled[1] = y;
								x++;
								continue;
							}

							if (data[x+1][y] == 'a')nextWaterCount++;

							if (data[x-1][y] == 't' && !(x-1 == alreadyControlled[0] && y == alreadyControlled[1])){
								alreadyControlled[0] = x;
								alreadyControlled[1] = y;
								x--;
								continue;
							}	
							if (data[x-1][y] == 'a')nextWaterCount++;

							if (data[x][y-1] == 't' && !(x == alreadyControlled[0] && y-1 == alreadyControlled[1])){
								alreadyControlled[0] = x;
								alreadyControlled[1] = y;
								y--;
								continue;
							}
							if (data[x][y-1] == 'a')nextWaterCount++;
						}		

						if ((nextLandCount == 0 && nextWaterCount == 4) || (nextLandCount == 1 && nextWaterCount == 6) ||
								(nextLandCount == 2 && nextWaterCount == 8) || (nextLandCount == 3 && nextWaterCount == 10)){
							stopControl = true;
							int [] toDelete = {0 , 0};
							water = water - toCheckHistory.size();
							while (iterator.hasNext()){
								toDelete = iterator.next();
								iterator.remove();
								data[toDelete[0]][toDelete[1]] = 't';
							}return false;
						}stopControl = true;
					}
				}
			}
		}
		return true;


	}
	 */	


	//CREAZIONE VEGETAZIONE
	private void createVegetable(char[][] data){
		int x , y;		
		int veget = 0;
		while ( veget < 40*(80*(SIZE*SIZE)/100)/100){
			x = this.intGenerator.nextInt(SIZE-1);
			y = this.intGenerator.nextInt(SIZE-1);
			if (x != 0 && y != 0){
				if (data[x][y] == 't') {
					data[x][y] = 'v';
					veget++;
				}
			}
		}
	}

	//CREAZIONE CAROGNE
	private void createMeat(char[][] data){
		int x , y;
		int carogne = 0;
		while (carogne < 20){
			x = this.intGenerator.nextInt(SIZE-1);
			y = this.intGenerator.nextInt(SIZE-1);
			if (x != 0 && y != 0){
				if (data[x][y] != 'v'){
					if (data[x][y] == 't') {
						data[x][y] = 'c';
						carogne++;
					}
				}
			}
		}		
	}




	/*
	 * Observer
	 */



	/**
	 * Ritorna la casella corrispondente o null
	 * @param x
	 * @param y
	 * @return
	 */
	public Box get(int x, int y) {
		try{
			return new Box(this.boxes.get(x, y));
		}
		catch (NullPointerException e){
			return null;
		}
	}

	/**
	 * Resistuisce una casella libera a caso
	 * @return
	 */
	public Box getRandomFreeBox() {
		Random r = new Random();
		int X, Y;
		do{
			X = r.nextInt(SIZE);
			Y = r.nextInt(SIZE);
		} while (this.dinos.containsKey(this.boxes.get(X, Y)) || ! this.boxes.get(X, Y).isLand());
		return this.boxes.get(X, Y);
	}

	public boolean walkable(Box b, Dino dino){
		if (b.isWater())
			return false;
		if (this.dinos.containsKey(b)){
			if (this.dinos.get(b).isHerb() && dino.isHerb())
				return false;
		}
		return true;
	}

	public boolean isFree(Box b){
		if (b.isWater())
			throw new IllegalArgumentException();

		if (this.dinos.containsKey(b))
			return false;
		return true;
	}

	/**
	 * Verifica se il dino può raggiungere la casella
	 * Se un erbivoro va dove c'è un erbivoro return FALSE
	 * @param movingDino
	 * @param destination
	 * @return
	 */
	public boolean reachable(Dino movingDino, Box destination) {
		if (this.computeDistance(this.boxes.get(movingDino.getX(), movingDino.getY()), this.boxes.get(destination.getX(), destination.getY()), movingDino) <= movingDino.maxDistance()){
			return true;
		}

		return false;
	}

	/**
	 * Calcola la distanza tra due caselle.
	 * Come prima cosa controlla la direzione da prendere. 
	 * In caso di caselle non attraversabili, cerca di aggirarle con il percorso minore
	 * DA VERIFICARE CON CASI LIMITE (TIPO DINO CIRCONDATO DA ACQUA)
	 * @param from
	 * @param to
	 * @return la lunghezza, in caselle, del percorso più breve tra due caselle
	 */
	public int computeDistance(Box from, Box to, Dino dino) {
		if (from.equals(to))
			return 0;
		if (! walkable(to, dino))
			return SIZE + 1;

		try{
			int offsetX = to.getX() - from.getX();
			int offsetY = to.getY() - from.getY();
			int X = from.getX(), Y = from.getY();
			int myDistance = 1;
			// Devo capire la direzione giusta
			try{
				if (offsetX > 0){ 

					if (offsetY > 0){ /* ###  N-E ### */
						X = from.getX() + 1;
						Y = from.getY() + 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X-horizon, Y), dino) &&
										walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X-horizon, Y), to, dino) < computeDistance(this.boxes.get(X, Y-horizon), to, dino)){
										X = X-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										Y = Y-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X-horizon, Y), dino)){
									foundPath = true;
									X = X-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									Y = Y-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}


					} else if (offsetY == 0){  /* ###  E ### */

						X = from.getX() + 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X, Y+horizon), dino) &&
										walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X, Y+horizon), to, dino) < computeDistance(this.boxes.get(X, Y-horizon), to, dino)){
										Y = Y+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										Y = Y-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X, Y+horizon), dino)){
									foundPath = true;
									Y = Y+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									Y = Y-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					} else { /* ###  S-E ### */

						X = from.getX() + 1;
						Y = from.getY() - 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X-horizon, Y), dino) &&
										walkable(this.boxes.get(X, Y+horizon), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X-horizon, Y), to, dino) < computeDistance(this.boxes.get(X, Y+horizon), to, dino)){
										X = X-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										Y = Y+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X-horizon, Y), dino)){
									foundPath = true;
									X = X-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X, Y+horizon), dino)){
									foundPath = true;
									Y = Y+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					}
				} else if (offsetX == 0){  

					if (offsetY > 0){ /* ###  N ### */ 

						Y = from.getY() + 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X+horizon, Y), dino) &&
										walkable(this.boxes.get(X-horizon, Y), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X+horizon, Y), to, dino) < computeDistance(this.boxes.get(X-horizon, Y), to, dino)){
										X = X+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										X = X-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X+horizon, Y), dino)){
									foundPath = true;
									X = X+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X-horizon, Y), dino)){
									foundPath = true;
									X = X-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					} else {  /* ###  S ### */

						Y = from.getY() - 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X+horizon, Y), dino) &&
										walkable(this.boxes.get(X-horizon, Y), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X+horizon, Y), to, dino) < computeDistance(this.boxes.get(X-horizon, Y), to, dino)){
										X = X+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										X = X-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X+horizon, Y), dino)){
									foundPath = true;
									X = X+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X-horizon, Y), dino)){
									foundPath = true;
									X = X-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					}
				} else { 
					if (offsetY > 0){  /* ###  N-W ### */

						X = from.getX() - 1;
						Y = from.getY() + 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X+horizon, Y), dino) &&
										walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X+horizon, Y), to, dino) < computeDistance(this.boxes.get(X, Y-horizon), to, dino)){
										X = X+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										Y = Y-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X+horizon, Y), dino)){
									foundPath = true;
									X = X+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									Y = Y-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					} else if (offsetY == 0){  /* ###  W ### */

						X = from.getX() - 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X, Y+horizon), dino) &&
										walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X, Y+horizon), to, dino) < computeDistance(this.boxes.get(X, Y-horizon), to, dino)){
										Y = Y+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										Y = Y-horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X, Y+horizon), dino)){
									foundPath = true;
									Y = Y+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X, Y-horizon), dino)){
									foundPath = true;
									Y = Y-horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					} else {  /* ###  S-W ### */

						X = from.getX() - 1;
						Y = from.getY() - 1;
						if (! walkable(this.boxes.get(X, Y), dino)){
							int horizon = 1;
							boolean foundPath = false;
							while (! foundPath){
								if (walkable(this.boxes.get(X+horizon, Y), dino) &&
										walkable(this.boxes.get(X, Y+horizon), dino)){
									foundPath = true;
									if (computeDistance(this.boxes.get(X+horizon, Y), to, dino) < computeDistance(this.boxes.get(X, Y+horizon), to, dino)){
										X = X+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									} else {
										Y = Y+horizon;
										myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
									}

								}
								else if (walkable(this.boxes.get(X+horizon, Y), dino)){
									foundPath = true;
									X = X+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else if (walkable(this.boxes.get(X, Y+horizon), dino)){
									foundPath = true;
									Y = Y+horizon;
									myDistance = computeDistance(from, this.boxes.get(X, Y), dino);
								}
								else horizon++;
							}
						}

					}
				}
			}catch (NullPointerException e){ // Ritorno un valore "infinito" DA TESTARE
				return SIZE + 1;
			}

			return myDistance + computeDistance(this.boxes.get(X, Y), to, dino);
		} catch (StackOverflowError e){
			System.out.println("Stack overflow");
			return SIZE + 1;
		}
	}

	/**
	 * Il giocatore asker richiede la mappa generale, con le proprie limitazioni
	 * Informazioni necessarie : buio, acqua, terra, vegetazione
	 * 
	 * @return oggetto UserMap appositamente creato
	 */
	/*
	 * Mantengo le info sulla parte esplorata da ogni tipo
	 * prendo solo le informazioni territoriali
	 */
	public UserMap getUserMap(Player asker) {
		if (this.userMaps.containsKey(asker)){
			return this.userMaps.get(asker);
		}

		BoxType[][] boxes = new BoxType[SIZE][SIZE];
		for (int i = 0;i < SIZE;i++)
			for (int j = 0;j < SIZE;j++)
				boxes[i][j] = BoxType.DARK;

		try{
			Dino d = asker.getDino(asker.getDinoList()[0]);
			for (int i = d.getX() - d.view();i <= d.getX() + d.view();i++){
				for (int j = d.getY() - d.view();j <= d.getY() + d.view();j++){
					if (i >= 0 && i < SIZE && j >= 0 && j < SIZE){
						Box b = this.boxes.get(i, j);
						if (b.isWater())
							boxes[i][j] = BoxType.WATER;
						else if (b.isVegetableBox()) {
							boxes[i][j] = BoxType.VEGE;
						} else
							boxes[i][j] = BoxType.LAND;
					}
				}
			}
		} catch (ArrayIndexOutOfBoundsException ex){
			throw new RuntimeException();
		}

		UserMap map = new UserMap(SIZE, 0, 0, boxes);
		this.userMaps.put(asker, map);
		return map;
	}


	/**
	 * Il giocatore asker richiede la visuale di un dinosauro, proprio o altrui
	 * Informazioni necessarie : acqua, terra, vegetazione con energia, carne con energia, dinosauri con id
	 *
	 * @return oggetto UserMap appositamente creato
	 */
	/*
	 * il dino sa quante caselle può vedere
	 * mi metto nella sua posizione e ciclo sulla sua visuale
	 * 
	 * poi valuto quali informazioni può vedere
	 */
	public UserMap getDinoVisual(Player asker, Dino dino) {
		UserMap map;
		BoxType[][] boxes = new BoxType[dino.view()*2 + 1][dino.view()*2 + 1];
		int[][] values = new int[dino.view()*2 + 1][dino.view()*2 + 1];
		int originX = (dino.getX() - dino.view() > 0) ? dino.getX() - dino.view() : 0;
		int originY = (dino.getY() - dino.view() > 0) ? dino.getY() - dino.view() : 0;

		for (int i = originX;i <= dino.getX() + dino.view();i++){
			for (int j = originY;j <= dino.getY() + dino.view();j++){
				if (i >= 0 && i < SIZE && j >= 0 && j < SIZE){
					Box b = this.boxes.get(i, j);
					int x = i - originX;
					int y = j - originY;
					if (b.isWater())
						boxes[x][y] = BoxType.WATER;
					else if (! this.isFree(b)){
						boxes[x][y] = BoxType.DINO;
						values[x][y] = this.dinos.get(b).getId();
					}
					else if (b.isMeatBox()){
						boxes[x][y] = BoxType.MEAT;
						values[x][y] = b.getFoodEnergy();
					}
					else if (b.isVegetableBox()){
						boxes[x][y] = BoxType.VEGE;
						values[x][y] = b.getFoodEnergy();
					}
					else
						boxes[x][y] = BoxType.LAND;
				}
			}
		}

		map = new UserMap(dino.view()*2 + 1, originX, originY, boxes);
		map.setValues(values);

		// AGGIORNO LA MAPPA UTENTE
		UserMap myMap = this.userMaps.get(asker);
		myMap.merge(map);

		return map;
	}


	/*
	 * Modificatori
	 */

	/**
	 * Aggiorna il contenuto di cibo nelle caselle
	 */
	public void updateFood() {
		for (Box b : this.foodBoxes){
			try{
				this.boxes.get(b.getX(), b.getY()).updateFoodEnergy();
			} catch (MeatExhaustedException e){
				this.foodBoxes.remove(b);
				Box newMeat = this.getRandomFreeBox();
				newMeat.putMeat();
				this.foodBoxes.add(newMeat);
			}
		}

	}
	/**
	 * Modifica la mappa aggiungendo un riferimento a dino nella casella
	 * @param child
	 * @param randomFreeBox
	 */
	public void putDino(Dino dino, Box location) {
		if (dino.isCarniv()){
			this.dinos.put(this.boxes.get(location.getX(), location.getY()), new Carnivorous((Carnivorous)dino));
		} else if (dino.isHerb()){
			this.dinos.put(this.boxes.get(location.getX(), location.getY()), new Herbivorous((Herbivorous)dino));
		}

	}

	/**
	 * Il dinosauro viene cancellato dalla mappa
	 * @param father
	 */
	public void removeDino(Dino dino) {
		if (this.dinos.containsValue(dino)){
			for (Box b : this.dinos.keySet()){
				if (this.dinos.get(b).equals(dino)){
					this.dinos.remove(b);
					return;
				}
			}
		}

	}


	/**
	 * Sposta il dinosauro in destination
	 * Se possibile LO FA MANGIARE
	 * Se c'è un dinosauro li fa combattere
	 * @param movingDino
	 * @param destination
	 */
	public void moveDino(Dino movingDino, Box destination) throws FightHappened{
		Box position = this.boxes.get(movingDino.getX(), movingDino.getY());
		Box dest = this.boxes.get(destination.getX(), destination.getY());

		if (this.reachable(movingDino, dest)){
			// CIBO
			if (movingDino.isCarniv() && dest.isMeatBox() || 
					movingDino.isHerb() && dest.isVegetableBox()){

				if (movingDino.isCarniv() && dest.isMeatBox()){
					this.foodBoxes.remove(dest);
					Box newMeat = this.getRandomFreeBox();
					newMeat.putMeat();
					this.foodBoxes.add(newMeat);
				}
				movingDino.eat(dest);
				dest.foodEaten();
			}

			// COMBATTIMENTO
			if (! this.isFree(dest)){
				Dino enemy = this.dinos.get(dest);
				// HO TROVATO IL DINO NEMICO
				Dino winner = movingDino.fight(enemy);
				if (! winner.equals(movingDino)){
					this.dinos.remove(position);
				} else {
					this.dinos.remove(dest);
					this.dinos.remove(position);
					this.dinos.put(dest, movingDino);
				}
				Integer idLoser = (winner.equals(movingDino)) ? enemy.getId() : movingDino.getId();
				throw new FightHappened(idLoser.toString());
			}

			// MOVIMENTO
			this.dinos.remove(position);
			this.dinos.put(dest, movingDino);

		}
	}

}
